package linkedlist;

/**
 * 反转链表
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 */
public class ReverseLinkedList {

  /**
   * 使用三个指针进行Reverse
   *
   * @param head
   * @return
   */
  public ListNode reverseList1(ListNode head) {
    if (head == null) {
      return head;
    }
    ListNode cur = head, pre = null, next;
    while (cur != null) {
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  }

  /**
   * 使用递归进行reverse
   * @param head
   * @return
   */
  public ListNode reverseList2(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode p = reverseList2(head.next);
    head.next.next = head;
    head.next = null;
    return p;
  }
}
